#ifndef _CRT_RBTREE_H
#define _CRT_RBTREE_H

#include <crt_atomic.h>
#include <crt_core.hpp>

#ifdef __cplusplus
extern "C" {
#endif

typedef struct _rbtree_node _rbtree_node_t;
typedef struct _rbtree_root _rbtree_root_t;

/*
2-byte alignment: requires addresses of 2, 4, 6, 8... ,
the last bit of the binary address is 0 (2 to the first power)

4 byte alignment: requires addresses of 4, 8, 12, 16... ,
the last two bits of the binary address are 0 (2 to the second power).
*/

#if (TARGET_BITS == ARCH_64BIT)
#pragma pack(push, 8)
#elif (TARGET_BITS == ARCH_32BIT)
#pragma pack(push, 4)
#else
#pragma pack(push, 1)
#endif

struct _rbtree_node {
    // parent->ptr
    //((struct _rbtree_node*)((r)->__rb_parent_color & ~3))
#if (TARGET_OS == OS_WIN)
#if (TARGET_BITS == ARCH_64BIT)
    // win64 --> long long
    uint64 __rb_parent_color;
#else
    uint32 __rb_parent_color;
#endif // (TARGET_BITS == ARCH_64BIT)
#else
    unsigned long __rb_parent_color;
#endif // (TARGET_OS == OS_WIN)

#define RB_RED      0
#define RB_BLACK    1
#define RB_SENTINEL 2
    struct _rbtree_node* rb_right;
    struct _rbtree_node* rb_left;
};

struct _rbtree_root {
    struct _rbtree_node* rb_node;
};

#pragma pack(pop)

#define __rb_parent(pc)   ((struct _rbtree_node*)(pc & ~3))
#define __rb_color(pc)    ((pc)&1)
#define __rb_is_black(pc) __rb_color(pc)
#define __rb_is_red(pc)   (!__rb_color(pc))

#define rb_color(rb)    __rb_color((rb)->__rb_parent_color)
#define rb_is_red(rb)   __rb_is_red((rb)->__rb_parent_color)
#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)

#define rb_parent(r) ((struct _rbtree_node*)((r)->__rb_parent_color & ~3))
#define RB_ROOT \
    (struct _rbtree_root) \
    { \
        NULL, \
    }
#define rb_entry(ptr, type, member) _container_of(ptr, type, member)

#define rb_entry_safe(ptr, type, member) _container_of(ptr, type, member)

#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)

#define RB_EMPTY_NODE(node) ((node)->__rb_parent_color == (unsigned long)(node))

#define RB_CLEAR_NODE(node) ((node)->__rb_parent_color = (unsigned long)(node))

void rb_insert_color(struct _rbtree_node*, struct _rbtree_root*);
void rb_erase(struct _rbtree_node*, struct _rbtree_root*);

struct _rbtree_node* rb_next(const struct _rbtree_node*);

struct _rbtree_node* rb_prev(const struct _rbtree_node*);

struct _rbtree_node* rb_first(const struct _rbtree_root*);

struct _rbtree_node* rb_last(const struct _rbtree_root*);

void rb_replace_node(struct _rbtree_node* victim, struct _rbtree_node* _new, struct _rbtree_root* root);

static_inline void rb_link_node(struct _rbtree_node* node, struct _rbtree_node* parent, struct _rbtree_node** rb_link)
{
    node->__rb_parent_color = (unsigned long)parent;
    node->rb_left = node->rb_right = NULL;
    *rb_link = node;
}

#ifdef __cplusplus
}
#endif

#endif
